741D - Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths - CodeForces Solution

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define endl '\n'
#define eps 0.000000001
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define IO ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
const int INF=0x3f3f3f3f;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
const int maxn=5e5+5;
int tot,head[maxn];
struct E{
    int to,next,w;
}edge[maxn<<1];
void add(int u,int v,int w){
    edge[tot].to=v;
    edge[tot].w=w;
    edge[tot].next=head[u];
    head[u]=tot++;
}
int dep[maxn],siz[maxn],son[maxn],dis[maxn],L[maxn],R[maxn],id[maxn],dfn;
void dfs1(int u,int f){
    dep[u]=dep[f]+1;
    siz[u]=1;
    L[u]=++dfn;
    id[dfn]=u;
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].to;
        if(v==f) continue;
        dis[v]=dis[u]^edge[i].w;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]]) son[u]=v;
    }
    R[u]=dfn;
}
int ans[maxn],flag,f[maxn*10];
void calc(int u,int fa){
    if(f[dis[u]]) ans[u]=max(ans[u],f[dis[u]]-dep[u]);
    rep(i,0,21){
        if(f[dis[u]^(1<<i)]){
            ans[u]=max(ans[u],f[dis[u]^(1<<i)]-dep[u]);
        }
    }
    f[dis[u]]=max(f[dis[u]],dep[u]);
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].to;
        if(v==fa||v==son[u]) continue;
        rep(j,L[v],R[v]){
            int x=id[j];
            if(f[dis[x]]) ans[u]=max(ans[u],f[dis[x]]+dep[x]-2*dep[u]);
            rep(k,0,21){
                if(f[dis[x]^(1<<k)]){
                    ans[u]=max(ans[u],f[dis[x]^(1<<k)]+dep[x]-2*dep[u]);
                }
            }
        }
        rep(j,L[v],R[v]) f[dis[id[j]]]=max(f[dis[id[j]]],dep[id[j]]);
    }
}
void dfs(int u,int fa,int keep){
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].to;
        if(v==son[u]||v==fa) continue;
        dfs(v,u,0);
        ans[u]=max(ans[u],ans[v]);
    }
    if(son[u]){
        dfs(son[u],u,1);
        ans[u]=max(ans[u],ans[son[u]]);
        flag=son[u];
    }
    calc(u,fa);
    flag=0;
    if(!keep){
        rep(i,L[u],R[u]) f[dis[id[i]]]=0;
    }
}
int main(){
    int n;cin>>n;mem(head,-1);
    rep(i,2,n){
        int x;char s;
        cin>>x>>s;
        add(i,x,1LL<<(s-'a'));
        add(x,i,1LL<<(s-'a'));
    }
    dfs1(1,0);
    dfs(1,0,0);
    rep(i,1,n) cout<<ans[i]<<" ";
}